It has been quite common within a data processing system to reserve a set of memory locations or registers to be used as an area for temporarily storing information. Such memory or registers have been referred to as a stack into which operands are pushed down (stored) and popped off (unloaded) on a last-in, first-out (LIFO) basis. The stack is divided into stack frames usually related to the programming concept of a procedure. A modular program, one having a plurality of procedures, will have multiple stack frames within a particular stack when a given procedure calls another procedure, e.g., returning jump, or calls itself, e.g., reentrant procedure call.
In prior art computer systems, the stack subdivisions or frames were commonly of a predetermined length and were not capable of being dynamically expanded or contracted. Accessing within a stack was accomplished by means of stack pointers, i.e., registers storing selected addresses of elements within the stack. A stack frame was created by storing addresses in the stack beginning with frame base relative address zero and incrementing in a numerically positive direction. One of the stack pointers was continually updated to reflect the address of the most recent entry in the stack frame relative to the base of the stack, i.e., the top of the stack pointer. Addressing of operands within the stack was performed by indexing from the current address of the top of the stack.
A problem has been found to arise when the only way to access operands within a stack frame is by indexing relative to the top of the frame. This is because any significant number of pushes or pops relating to a stack frame results in a continual change in the address of other operands in the stack relative to the top of the stack. As an example, a new stack frame is often created when a call is made from one procedure to a different procedure within a program. A call is accompanied by a number of parameters or operands transferred by the calling procedure to be stored in the stack frame created for the called procedure. These operands may contain the return address in the calling procedure as well as specific values for certain parameters. If, in the course of performing the called procedure, numerous entries are pushed onto the stack or popped off of the stack it may be impossible to determine the proper index relative to the top of the stack for addressing the return address to the calling routine. Such a problem will arise when the called procedure does not pop off all of the entries in its stack frame prior to returning to the calling procedure.
There is a second problem attendant with the prior art stack mechanisms. This arises from the common practice of allocating a fixed number of locations for each stack frame. This poses an artificial constraint on the stack mechanism and results in inefficient use of the memory or registers set aside to store the stack. For example, if a stack frame corresponding to a given procedure only requires a few entries, then the remaining entries in the frame will go unused and result in a significant waste of valuable memory space. In addition, some stack frames may require more space than what is normally allocated and, therefore, a stack overflow will occur. Finally, the selection of the size of the individual stack frames is commonly selected to minimize the number of stack overflows and therefore, has been commonly selected to be larger than necessary. This contributes to the inefficient use of the memory locations allocated for the system stack.